package edu.uestc.gene.test;

public class QuickSort {
	public static int[] a = { 11, 43, 3, 12, 1, 64, 33, 6, 42, 12 };

	// 分割的位置
	public static int partition(int left, int right) {
		// 枢纽，一般定义为数组最后一个数
		int pivot = a[right];
		int leftptr = left - 1;
		int rightptr = right;
		while (true) {
			while (a[++leftptr] < pivot)
				;
			while (rightptr > 0 && a[--rightptr] > pivot)
				;
			if (leftptr >= rightptr) {
				break;
			} else {
				// 每一次查找后，符合条件，就交换
				swap(leftptr, rightptr);
			}
		}
		// 一次分割完后，最后，把枢纽的数和左指针的数交换，这样，左指针的数大于左边的，小于右边的数
		swap(leftptr, right);
		return leftptr;
	}

	public static void recSort(int left, int right) {
		if (right - left <= 0) {
			return;
		} else {
			int partition = partition(left, right);
			// 调用一次分割，则递归执行分割的左右两部分
			recSort(left, partition - 1);
			recSort(partition + 1, right);
		}
	}

	public static void swap(int n, int m) {
		int temp;
		temp = a[n];
		a[n] = a[m];
		a[m] = temp;
	}

	public void display() {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		// QuickSort sort = new QuickSort();
		// sort.display();
		// sort.recSort(0, sort.a.length - 1);
		// sort.display();
	}

}